package com.kznnc.data_structure.structure.linkedStructure;

/**
 * @Description 基于虚拟节点的单向链表
 * 怎么判断头结点   尾结点 尾结点的next指针为null
 * @Author houchenkai
 * @Created Date: 2021/3/31 18:28
 * @ClassName
 */
public class LinkedStructure {
    /**
     * 链表的头
     */
    private Node first;
    /**
     * 链表的尾
     */
    private Node last;
    /**
     * 虚拟节点
     */
    private Node dummy;

    public LinkedStructure() {
    }

    public void insertFirst(Integer data) {
        Node newNode = new Node(data);
        if (first == null) {
            first = newNode;
            last = first;
        } else {
            newNode.next = first;
            first = newNode;
        }
        //维护虚拟节点和头结点的指针
        dummy = new Node(null);
        dummy.next = first;
    }

    public void insertLast(Integer data) {
        Node newNode = new Node(data);
        if (last == null) {
            dummy = new Node(null);
            first = newNode;
            last = newNode;
            dummy.next = first;
        } else {
            last.next = newNode;
            last = newNode;
        }
    }

    public void remove(Integer data) {
        for (Node node = dummy; node != null; node = node.next) {
            // 此处能获取到当前节点 去判断当前节点的下个节点是否是要删除的元素
            // 如果用当前元素比较后是当前元素，无法获取到执行当前元素的上一个元素的指针
            if (node.next.data.equals(data)) {
                if (node.next.equals(first)) {
                    dummy = first.next;
                    first = node.next.next;
                } else if (node.next.equals(last)) {
                    node.next = null;
                    last = node;
                } else {
                    node.next = node.next.next;
                }
                break;
            }
        }
    }

    public void update(Integer data, Integer newData) {
        // 因为比较的是当前 node 的下一个元素 所以当 当前元素的下一个元素为null
        //  node.next == null 时 说明已经在上次比较过last节点 所以循环结束
        // 循环只能在 node.next != null 的时候进行
        for (Node node = dummy; node.next != null; node = node.next) {
            // 此处能获取到当前节点 去判断当前节点的下个节点是否是要删除的元素
            // 如果用当前元素比较后是当前元素，无法获取到执行当前元素的上一个元素的指针
            if (node.next.data.equals(data)) {
                node.next.data = newData;
                break;
            }
        }
    }

    class Node {
        private Integer data;
        private Node next;

        public Node(Integer data) {
            this.data = data;
            this.next = null;
        }

        public Integer getData() {
            return data;
        }

        public void setData(Integer data) {
            this.data = data;
        }

        public Node getNext() {
            return next;
        }

        public void setNext(Node next) {
            this.next = next;
        }
    }


    public static void main(String[] args) {
        LinkedStructure linkedStructure = new LinkedStructure();

        for (int i = 0; i < 5; i++) {
            linkedStructure.insertLast(i);
        }
        for (Node node = linkedStructure.dummy; node.next != null; node = node.next) {
            System.out.println(node.next.data);
        }
    }

}
